package _05_二叉树;

import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode-cn.com/problems/path-sum-iii/
 * @Author: haogege
 * @Date: 2021/9/28
 */
public class _437_路径总和III {

    private Map<Integer, Integer> map = new HashMap<>();


    // 前缀和计算
    public int pathSum(TreeNode root, int targetSum) {
        // Hash表默认存储值
        map.put(0, 1);
        return dfs(root, 0, targetSum);
    }

    // 保存遍历到的前缀和
    public int dfs(TreeNode root, int total, int target) {
        if (root == null) return 0;
        total += root.val;
        // 查询前面是否存在，等于total - target
        int ret = map.getOrDefault(total - target, 0);
        // 保存当前前缀和
        map.put(total, map.getOrDefault(total, 0) + 1);
        ret += dfs(root.left, total, target);
        ret += dfs(root.right, total, target);
        map.put(total, map.getOrDefault(total, 0) - 1);
        return ret;
    }

    // 对每个遍历到的节点，进行和判断
    // 如何进行和判断，向下扫描。发现等于targetSum total++
    public int pathSum1(TreeNode root, int targetSum) {
        if (root == null) return 0;
        // 以当前节点，为根节点获取目标值的可能
        int res = rootSum(root, targetSum);
        res += pathSum(root.left, targetSum);
        res += pathSum(root.right, targetSum);
        return res;
    }

    private int rootSum(TreeNode root, int targetSum) {
        if (root == null) return 0;
        int res = 0;
        if (root.val == targetSum) {
            res++;
        }
        res += rootSum(root.left, targetSum - root.val);
        res += rootSum(root.right, targetSum - root.val);
        return res;
    }

}
